Lab 8: Social Network with Graphs

The Goal 🎯

  • The Model: A simple social network.
    • Users are represented as nodes in a graph.
    • Friendships are undirected edges.
  • The Task: Process a series of commands to build and query the network.

The Representation 💾

We will use an Adjacency List to store the graph.

It's an array of lists. The list at index `i` stores all the friends of user `i`.

// Friendships: (0,1), (0,2), (1,2)
adj = [
0: [1, 2],
1: [0, 2],
2: [0, 1],
3: [],
]

The Operations ⚙️

You will implement four commands:

  • add u v

    Add a friendship.

  • degree u

    Count friends of user u.

  • isfriend u v

    Check if u and v are friends.

  • count_greater x

    Count users with > x friends.